﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/find-k-closest-elements/
/*
题目描述：
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
 

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]
 

提示：
1 <= k <= arr.length
1 <= arr.length <= 104
arr 按 升序 排列
-104 <= arr[i], x <= 104。
*/

// 开始解题：
// 方法1——排序再排序
int g_val = 0;
// 先写一个函数，比较两个整数那个更接近x
int cmp1(const void* p1, const void* p2) {
    int a = *((int*)p1);
    int b = *((int*)p2);
    if (abs(a - g_val) == abs(b - g_val)) {
        return a - b;
    }
    else {
        return abs(a - g_val) - abs(b - g_val);
    }
}

// 再写一个函数，比较两个整数的大小
int cmp2(const void* p1, const void* p2) {
    return *((int*)p1) - *((int*)p2);
}

int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
    g_val = x;
    // 先将数组按照更接近x的顺序排序
    qsort(arr, arrSize, sizeof(int), cmp1);
    // 再将前k个元素按照从大到小的顺序排序
    qsort(arr, k, sizeof(int), cmp2);
    int* answer = (int*)malloc(k * sizeof(int));
    if (NULL == answer) {
        perror("malloc fail\n");
        return NULL;
    }
    // 拷贝数组arr的前k个元素到answer
    memcpy(answer, arr, k * sizeof(int));
    *returnSize = k;
    return answer;
}